package demo.exam;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test02 {

	public static void main(String[] args) {
		System.out.print(doAction(6, 6, Arrays.asList(
				Arrays.asList("S", "B", "B", "B", "B", "B"),
				Arrays.asList("B", "X", "X", "X", "X", "B"),
				Arrays.asList("B", "B", "X", "B", "B", "B"),
				Arrays.asList("X", "B", "B", "X", "X", "B"),
				Arrays.asList("B", "X", "B", "B", "X", "B"),
				Arrays.asList("B", "B", "X", "B", "E", "B"))));
	}

	private static int doAction(int m, int n, List<List<String>> area) {
		ArrayList<ArrayList<Integer[]>> result = new ArrayList<ArrayList<Integer[]>>();

		// 初始化 m * n
		for (int i = 0; i < m; i++) {
			ArrayList<Integer[]> row = new ArrayList<Integer[]>();
			List<String> rowArea = area.get(i);
			result.add(row);
			for (int j = 0; j < n; j++) {
				if (rowArea.get(j).equals("S")) {
					row.add(new Integer[] { 1, 0 });
				} else {
					row.add(new Integer[] { 0, 0 });
				}
			}
		}

		int minMove = 0;
		boolean changed = true;
		while (changed) {
			// printTable(m, n, result);
			changed = false;
			for (int i = 0; i < m; i++) {
				ArrayList<Integer[]> row = result.get(i);
				for (int j = 0; j < n; j++) {
					Integer[] cell = row.get(j);
					int value = cell[0];
					int direction = cell[1]; // 0: start, 1: top, 2: down, 3: left, 4: right
					int newDirection = 0;

					if (value > 0) {
						if (j > 0) {
							String cellArea = area.get(i).get(j - 1);
							if (!cellArea.equals("X")) {
								newDirection = 3;
								int newValue = calcValue(value, direction, newDirection);
								int cellValue = result.get(i).get(j - 1)[0];
								if (newValue < cellValue || cellValue == 0) {
									result.get(i).set(j - 1, new Integer[] { newValue, newDirection });
									changed = true;
									if (cellArea.equals("E") && (minMove == 0 || minMove > newValue)) {
										minMove = newValue;
									}
								}
							}
						}
						if (j < n - 1) {
							String cellArea = area.get(i).get(j + 1);
							if (!cellArea.equals("X")) {
								newDirection = 4;
								int newValue = calcValue(value, direction, newDirection);
								int cellValue = result.get(i).get(j + 1)[0];
								if (newValue < cellValue || cellValue == 0) {
									result.get(i).set(j + 1, new Integer[] { newValue, newDirection });
									changed = true;
									if (cellArea.equals("E") && (minMove == 0 || minMove > newValue)) {
										minMove = newValue;
									}
								}
							}
						}
						if (i > 0) {
							String cellArea = area.get(i - 1).get(j);
							if (!cellArea.equals("X")) {
								newDirection = 1;
								int newValue = calcValue(value, direction, newDirection);
								int cellValue = result.get(i - 1).get(j)[0];
								if (newValue < cellValue || cellValue == 0) {
									result.get(i - 1).set(j, new Integer[] { newValue, newDirection });
									changed = true;
									if (cellArea.equals("E") && (minMove == 0 || minMove > newValue)) {
										minMove = newValue;
									}
								}
							}
						}
						if (i < m - 1) {
							String cellArea = area.get(i + 1).get(j);
							if (!cellArea.equals("X")) {
								newDirection = 2;
								int newValue = calcValue(value, direction, newDirection);
								int cellValue = result.get(i + 1).get(j)[0];
								if (newValue < cellValue || cellValue == 0) {
									result.get(i + 1).set(j, new Integer[] { newValue, newDirection });
									changed = true;
									if (cellArea.equals("E") && (minMove == 0 || minMove > newValue)) {
										minMove = newValue;
									}
								}
							}
						}
					}
				}
			}
		}

		return minMove - 1;
	}

	private static int calcValue(int oldValue, int oldDirection, int newDirection) {
		if (oldDirection == 0) {
			return oldValue + 1;
		}
		if (oldDirection == newDirection) {
			return oldValue + 1;
		}
		return oldValue + 2;
	}

	// private static void printTable(int m, int n, ArrayList<ArrayList<Integer[]>> result) {
	// 	for (int i = 0; i < m; i++) {
	// 		for (int j = 0; j < n; j++) {
	// 			Integer[] cell = result.get(i).get(j);
	// 			System.out.print(cell[0] + ":" + cell[1] + ", ");
	// 		}
	// 		System.out.println("");
	// 	}
	// }
}
